package org.lep.leetcode.palindrome.validpalindrome;

/**
 * Source : https://oj.leetcode.com/problems/valid-palindrome/
 *
 * Created by lverpeng on 2017/8/22.
 *
 * Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
 *
 * For example,
 * "A man, a plan, a canal: Panama" is a palindrome.
 * "race a car" is not a palindrome.
 *
 * Note:
 * Have you consider that the string might be empty? This is a good question to ask during an interview.
 *
 * For the purpose of this problem, we define empty string as valid palindrome.
 *
 *
 */
public class ValidPalindrome {

    /**
     * 判断一个字符串是否是回文字符串，只判断字符串里面的字母和数字
     *
     * @param str
     * @return
     */
    public boolean valid (String str) {
        int left = 0;
        int right = str.length()-1;
        while (left <= right) {
            // 过滤左边非数字字母
            while (left < str.length() && !isAlphanumeric(str.charAt(left))) {
                left++;
            }
            // 过滤右边非数字字母
            while (0 < right && !isAlphanumeric(str.charAt(right))) {
                right--;
            }
            if (left >= right) {
                return true;
            }
            if (Character.toLowerCase(str.charAt(left++)) != Character.toLowerCase(str.charAt(right--))) {
                return false;
            }
        }
        return true;
    }


    public boolean isAlphanumeric (char c) {
        if ((c >= 48 && c <= 57) || ((c >= 65 && c <= 90) || (c >= 97 && c<= 122))) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        ValidPalindrome validPalindrome = new ValidPalindrome();
        System.out.println(validPalindrome.valid("A man, a plan, a canal: Panama") + "-----true");
        System.out.println(validPalindrome.valid("race a car") + "-----false");
    }

}
